﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using CompleterLib.AbstractTypes;
using CompleterLib.Util;
using Roslyn.Compilers;
using Roslyn.Compilers.Common;
using Roslyn.Compilers.CSharp;
using SD.Tools.Algorithmia.GeneralDataStructures;
using Util;

namespace CompleterLib
{
    public class Completer
    {
        private readonly SemanticModel semModel;
        private readonly Lazy<TypeSymbol> containingType;
        private readonly int position;
        private readonly Lazy<AbstractTypeInferencer> absTypes;
        private readonly CancellationToken cancellationToken;

        // Coefficients in ranking formula.
        // Written in style of properties to allow switch to properties without code change.
        private const int TypeDistanceCoefficient = 10;
        private const int AbstractTypeDistanceCoefficient = TypeDistanceCoefficient;
        private const int DepthCoefficient = 20;
        private const int EmptyPrefixCoefficient = 1;
        private const int EmptyCoefficient = 1;
        private const int GlobalCoefficient = 2 * DepthCoefficient;

        public Completer(SemanticModel semModel, int position,
                         CancellationToken cancellationToken = default(CancellationToken))
        {
            this.semModel = semModel;
            this.position = position;
            // TODO How to get containing type (for type of "this")?
            this.containingType = new Lazy<TypeSymbol>(() => semModel.GetContainingTypeAt(position));
            this.absTypes = new Lazy<AbstractTypeInferencer>(
                () => new AbstractTypes.AbstractTypeInferencer(semModel, position, cancellationToken));
            this.cancellationToken = cancellationToken;
            cancellationToken.ThrowIfCancellationRequested();
        }

        protected IEnumerable<Completion> GetLookups(TypeSymbol type, bool fieldsOnly)
        {
            if (type != null && !(type is ErrorTypeSymbol))
            {
                foreach (var mem in type.GetAllMembers().Cast<Symbol>())
                {
                    if (!mem.IsStatic && mem.CanBeReferencedByName /*&& !mem.IsSynthesized*/)
                    {
                        if (mem is FieldSymbol && semModel.IsAccessible(position, mem))
                        {
                            var field = mem as FieldSymbol;
                            bool isLvalue = !(field.IsConst || field.IsReadOnly);
                            yield return new Completion(field.Name, field.Type,
                                isLvalue, true, field.AsTypeTerm());
                        }
                        else if (mem is PropertySymbol
                            && semModel.IsAccessible(position, mem))
                        {
                            var prop = mem as PropertySymbol;
                            bool isLValue = !prop.IsReadOnly && prop.SetMethod != null
                                && semModel.IsAccessible(position, prop.SetMethod);
                            bool isRValue = !prop.IsWriteOnly && prop.GetMethod != null
                                && semModel.IsAccessible(position, prop.GetMethod);
                            // Only want actual properties here, not indexers.
                            if ((!isRValue || prop.GetMethod.Parameters.Count == 0) &&
                                (!isLValue || prop.SetMethod.Parameters.Count == 1))
                            {
                                yield return new Completion(prop.Name, prop.Type,
                                    isLValue, isRValue, prop.AsTypeTerm());
                            }
                        }
                        else if (mem is MethodSymbol && !fieldsOnly
                            && semModel.IsAccessible(position, mem))
                        {
                            var meth = mem as MethodSymbol;
                            // Blacklist GetType because it hurts results a lot.
                            if (!meth.Parameters.Any()
                                && !meth.Name.Equals("GetType")
                                && !meth.Name.Equals("Clone")
                                && !meth.Name.Equals("MemberwiseClone"))
                            {
                                yield return new Completion(meth.Name + "()", meth.ReturnType,
                                    new ReturnTypeTypeTerm(meth));
                            }
                        }
                    }
                }
            }
        }
        protected IEnumerable<Completion> GetLookups(TypeSymbol type, bool fieldsOnly,
            TypeSymbol retType)
        {
            return GetLookups(type, fieldsOnly)
                .Where(c => retType.IsAssignableFromOrUnknown(c.Type, semModel));
        }

        protected IEnumerable<Completion> GetLocals(IEnumerable<Symbol> skip)
        {
            skip = skip.Where(s => s is LocalSymbol || s is ParameterSymbol).ToList();
            return from sym in semModel.LookupSymbols(position)
                   where (sym is LocalSymbol || sym is ParameterSymbol) && !skip.Contains(sym)
                   select new Completion(sym, absTypes.Value.GetTypeTermFor(sym));
        }

        protected IEnumerable<Completion> GetStaticFields(TypeSymbol containingType, IEnumerable<Symbol> skip)
        {
            skip = skip.Where(s => s is FieldSymbol || s is PropertySymbol).ToList();
            return from sym in semModel.LookupSymbols(position)
                   where sym.IsStatic
                      && (sym is FieldSymbol || sym is PropertySymbol)
                      && !skip.Contains(sym)
                      && sym.ContainingType.IsAssignableFrom(containingType, semModel)
                   select new Completion(sym, DepthCoefficient, absTypes.Value.GetTypeTermFor(sym));
        }

        protected IEnumerable<Completion> GetGlobals()
        {
            return from sym in semModel.GetGlobals()
                   where semModel.IsAccessible(position, sym)
                   select new Completion(sym, GlobalCoefficient,
                                         absTypes.Value.GetTypeTermFor(sym));
        }

        private IEnumerable<IMethodSymbolWrapper> GetMethodsForArgs(
                List<TypeSymbol> argTypes, TypeSymbol parentStaticType = null)
        {
            // TODO Is this the right behavior? Return no methods for no arg types?
            //      Alternatively, could return all methods... but that's not really informative.
            //if (argTypes.Count > 0)
            //{
            // TODO This returns static methods not referenced by usings... that seems good.
            IEnumerable<MethodSymbol> methods;
            if (parentStaticType == null)
            {
                methods = semModel.GetAllStaticMethodsForArgs(argTypes)
                    .Concat(argTypes.Select(at => at.GetAllInstanceMethods()).Concat());
            }
            else
            {
                methods = parentStaticType.GetMembers()
                    .Where(sym => sym is MethodSymbol && sym.IsStatic && sym.CanBeReferencedByName)
                    .Cast<MethodSymbol>();
            }
            foreach (MethodSymbol meth in methods
                                         .Where(sym => semModel.IsAccessible(position, sym)))
            {
                // TODO This is inefficient.
                if (meth.MethodKind.Equals(MethodKind.Constructor))
                {
                    // Don't recommend constructors on abstract types.
                    if (meth.ContainingType.IsAbstract)
                    {
                        continue;
                    }
                }
                else if (!meth.IsStatic)
                {
                    // Ensure some arg could be the receiver.
                    if (!argTypes.Any(at => meth.ContainingType.IsAssignableFrom(at, semModel)))
                    {
                        continue;
                    }
                }
                // For every arg, ensure it could be used as some parameter.
                if (meth.Parameters.Count > 0)
                {
                    var paramTypes = meth.Parameters.AsEnumerable().Select(p => p.Type).ToList();
                    if (!argTypes.All(at => paramTypes.Any(p =>
                        p.IsAssignableFrom(at, semModel)
                        || !meth.IsStatic && meth.ContainingType.IsAssignableFrom(at, semModel))))
                    {
                        continue;
                    }
                }
                yield return new MethodSymbolWrapper(meth);
            }
            //}
        }
        private IEnumerable<List<SortedSet<Completion>>> GetAssignmentsForArgs(
            IMethodSymbolWrapper method,
            List<KeyValuePair<TypeSymbol, SortedSet<Completion>>> args)
        {
            var paramTypes = method.ParameterTypes;
            return GetAssignmentsForArgs(paramTypes, args, method.IsStatic);
        }
        private IEnumerable<List<SortedSet<Completion>>> GetAssignmentsForArgs(IList<TypeWithRefKind> parameters,
            List<KeyValuePair<TypeSymbol, SortedSet<Completion>>> args, bool isStatic)
        {
            if (args.Count == 0)
            {
                return Enumerable
                    .Repeat<SortedSet<Completion>>(
                        EmptyCompletion.Instance.SingletonSortedSet<Completion>(),
                            parameters.Count)
                    .ToList().Singleton();
            }
            else
            {
                return args.Select(a => parameters
                                .Select(p => p.IsCompatible(a.Value.First(), semModel))
                                              .ToArray())
                                .ToArray()
                                .EnumerateMaximumMatchings()
                                .Where(matching => isStatic || matching[0] != -1)
                                .Select(matching =>
                                    matching.Select(i => i == -1
                                        ? EmptyCompletion.Instance.SingletonSortedSet<Completion>()
                                        : args[i].Value)
                                    .ToList());
            }
        }

        public IEnumerable<Completion> GetCompletions(ExpressionSyntax exp)
        {
            bool lvalue = exp.Parent.Kind.Equals(SyntaxKind.AssignExpression)
                    && (exp.Parent as BinaryExpressionSyntax).Left == exp;
            TypeSymbol assignFrom = null;
            if (lvalue)
            {
                assignFrom = semModel.GetTypeInfo((exp.Parent as BinaryExpressionSyntax).Right).Type;
            }
            MethodCache.SignalNewSemanticModel(semModel, cancellationToken);
            var res = new LazyCompletionsGetter(_GetCompletions(exp, exp.GetRetType(semModel))
                // TODO ... or what if it isn't an rvalue?
                .Where(c => !(c is Completion)
                    || (lvalue && (c as Completion).IsLValue
                        && (c as Completion).Type.IsAssignableFromOrUnknown(assignFrom, semModel))
                    || (!lvalue && (c as Completion).IsRValue)))
                .EnumerateCompletions();
            MethodCache.SignalFinishedWithSemanticModel(semModel);
            return res;
        }
        private IEnumerable<Completion> GetCompletions(IEnumerable<CompleterReturnValue> comps,
            TypeSymbol retType = null, bool isLValue = false, TypeSymbol assignFrom = null)
        {
            var res = new LazyCompletionsGetter(comps
                // TODO ... or what if it isn't an rvalue?
                .Where(c => !(c is Completion)
                    || (isLValue && (c as Completion).IsLValue
                        && (c as Completion).Type.IsAssignableFromOrUnknown(assignFrom, semModel))
                    || (!isLValue && (c as Completion).IsRValue)))
                .EnumerateCompletions();
            return res;
        }

        private IEnumerable<CompleterReturnValue> _GetCompletions(
                ExpressionSyntax exp, TypeSymbol retType = null)
        {
            IEnumerable<CompleterReturnValue> res;
            if (exp != null && !exp.IsPartial(semModel))
            {
                res = new Completion(exp, semModel,
                                     absTypes.Value.GetTypeTermFor(exp, semModel)
                    ).SingletonList();
            }
            else if (exp is MemberAccessExpressionSyntax)
            {
                var lookup = exp as MemberAccessExpressionSyntax;
                if (new string[] { "m", "mUnknown" }.Contains(lookup.Name.PlainName)
                    && !semModel.GetTypeInfo(exp).Type.IsValidType())
                {
                    IList<ExpressionSyntax> args;
                    TypeSymbol parentStaticType = semModel.GetSymbolInfo(
                        lookup.Expression).Symbol as TypeSymbol;

                    if (parentStaticType == null)
                    {
                        args = lookup.Expression.SingletonList();
                    }
                    else
                    {
                        args = new List<ExpressionSyntax>();
                    }

                    res = GetCompletionsUnknownMethod(args, retType, parentStaticType);
                }
                else
                {
                    res = GetCompletions(lookup, retType);
                }
            }
            else if (exp is InvocationExpressionSyntax)
            {
                res = GetCompletions(exp as InvocationExpressionSyntax, retType);
            }
            else if (exp is ObjectCreationExpressionSyntax)
            {
                res = GetCompletions(exp as ObjectCreationExpressionSyntax, retType);
            }
            else if (exp is IdentifierNameSyntax || exp is TypeSyntax)
            {
                // Can only have a partial identifier if it is xx or xxUnknown.
                var declSyms = exp.AncestorsAndSelf()
                    .Where(e => e is VariableDeclaratorSyntax)
                    .Select(e => semModel.GetDeclaredSymbol(e as VariableDeclaratorSyntax))
                    .ToList();

                var containingType = this.containingType.Value;
                var containingMethod = exp.AncestorsAndSelf()
                    .Where(e => e is MethodDeclarationSyntax || e is AccessorDeclarationSyntax || e is ConstructorDeclarationSyntax)
                    .Select(e => semModel.GetDeclaredMethodSymbol(e))
                    .FirstOrDefault();
                bool isStatic = containingMethod == null || containingMethod.IsStatic;
                IEnumerable<CompleterReturnValue> fieldsPart;
                IEnumerable<CompleterReturnValue> globalsPart;
                IEnumerable<CompleterReturnValue> methodsPart;
                if (isStatic)
                {
                    // in static context
                    fieldsPart = new MinFutureScore(DepthCoefficient)
                                .Cons(GetStaticFields(containingType, declSyms)
                                     .Cast<CompleterReturnValue>());
                    globalsPart = new MinFutureScore(GlobalCoefficient)
                                 .Cons(GetGlobals()
                                      .Except(fieldsPart, CompletionTextComparer.Instance)
                                      .Cast<CompleterReturnValue>());
                }
                else
                {
                    // in instance context
                    fieldsPart = new Completion("this", containingType,
                        false, true, 0, new AnonymousTypeTerm()).Singleton();
                    globalsPart = new MinFutureScore(GlobalCoefficient)
                                 .Cons(GetGlobals()
                                      .Cast<CompleterReturnValue>());
                }
                // TODO Add GlobalCoefficient to score
                methodsPart = LazyCompletionsGetter.AddToScore(
                    GetCompletions(null as InvocationExpressionSyntax, retType),
                    GlobalCoefficient);

                // TODO Is Distinct() too expensive? Really only need to get rid of
                //      static fields in a static context...
                res = GetCompletions(new LazyCompletionsGetter(
                                        GetLocals(declSyms)
                                       .Concat(fieldsPart)
                                       .Concat(globalsPart)
                                       .Concat(methodsPart)
                                       ),
                                     false, true, retType);
            }
            else if (exp is BinaryExpressionSyntax)
            {
                if (exp.Kind.Equals(SyntaxKind.AssignExpression))
                {
                    res = GetAssignmentCompletions(exp as BinaryExpressionSyntax, retType);
                }
                else if (exp.Kind.Equals(SyntaxKind.AsExpression))
                {
                    res = GetAsExpressionCompletions(exp as BinaryExpressionSyntax);
                }
                else if (exp.Kind.Equals(SyntaxKind.CoalesceExpression))
                {
                    res = GetCoalesceCompletions(exp as BinaryExpressionSyntax, retType);
                }
                else
                {
                    res = GetCompletions(exp as BinaryExpressionSyntax, retType);
                }
            }
            else if (exp is CastExpressionSyntax)
            {
                var cast = (CastExpressionSyntax)exp;
                return _GetCompletions(cast.Expression,
                                       semModel.GetTypeInfo(cast.Type).Type);
            }
            else if (exp == null)
            {
                // TODO This is messy to special case null here...
                // null is special cased to mean "this" for implicit this.
                res = new Completion("this", containingType.Value,
                        false, true, 0, new AnonymousTypeTerm()).SingletonList();
            }
            else
            {
                res = new Completion(exp, semModel,
                                     absTypes.Value.GetTypeTermFor(exp, semModel)
                    ).SingletonList();
            }
            if (retType.IsValidType()
                && (exp.Parent is ReturnStatementSyntax
                    || (exp.Parent is EqualsValueClauseSyntax
                        && exp.Parent.Parent is VariableDeclaratorSyntax)
                    || exp.Parent.Kind.Equals(SyntaxKind.AssignExpression)
                    || exp is TypeSyntax))
            {
                // TODO Do this in any other places?
                // Add type distance to declared type.
                return WithTypeDistance(res, retType,
                    exp.GetRetTypeTerm(semModel, absTypes.Value));
            }
            else
            {
                return res;
            }
        }

        private IEnumerable<CompleterReturnValue> GetCompletions(InvocationExpressionSyntax call, TypeSymbol retType = null)
        {
            List<ExpressionSyntax> args = new List<ExpressionSyntax>();

            // Shorthand for m() query.
            if (call == null)
            {
                return GetCompletionsUnknownMethod(args, retType);
            }

            var kind = call.GetInvocationExpressionKind(semModel);

            var method = call.Expression;
            var methodSymbol = semModel.GetSymbolInfo(method).Symbol;

            var methodAccess = method as MemberAccessExpressionSyntax;
            //TypeSymbol staticParent = null;
            bool hasParent = false;
            if (methodAccess != null)
            {
                var parent = methodAccess.Expression;
                if (!(kind.Equals(InvocationExpressionKind.UNKNOWN_STATIC)
                        || kind.Equals(InvocationExpressionKind.SEMIKNOWN_STATIC)
                        || kind.Equals(InvocationExpressionKind.KNOWN_STATIC)))
                {
                    args.Add(parent);
                    hasParent = true;
                }
            }

            var argList = call.ArgumentList;
            args.AddRange(argList.Arguments.Select(arg => arg.Expression));
            if (kind.Equals(InvocationExpressionKind.KNOWN)
                || kind.Equals(InvocationExpressionKind.KNOWN_STATIC))
            {
                return GetCompletionsKnownMethod(MethodSymbolWrapper.Create(methodSymbol as MethodSymbol, hasParent), args);
            }
            else if (kind.Equals(InvocationExpressionKind.UNKNOWN))
            {
                return GetCompletionsUnknownMethod(args, retType);
            }
            else if (kind.Equals(InvocationExpressionKind.UNKNOWN_STATIC))
            {
                var parentType = semModel.GetSymbolInfo(methodAccess.Expression).Symbol as TypeSymbol;
                return GetCompletionsUnknownMethod(args, retType, parentType);
            }
            else if (kind.Equals(InvocationExpressionKind.SEMIKNOWN)
                || kind.Equals(InvocationExpressionKind.SEMIKNOWN_STATIC))
            {
                return GetCompletionsSemiKnownMethod(
                    semModel.GetMethodGroup(method).Select(sym => MethodSymbolWrapper.Create(sym, hasParent))
                                          .ToList<IMethodSymbolWrapper>(),
                    args, retType);
            }
            else
            {
                /*string unknownCall = "unknownM(" + args.Select(arg => arg.GetText())
                    .CommaSeparated() + ")";
                return new List<Completion> { new Completion(unknownCall) };*/
                return new List<Completion> { new Completion(call, semModel,
                                                             absTypes.Value.GetTypeTermFor(call, semModel)) };
            }
        }

        private static string[] unknowns = new string[] { "f", "ff", "x", "xx" };
        private IEnumerable<CompleterReturnValue> GetCompletions(LazyCompletionsGetter parents,
            bool fieldsOnly, bool pural, TypeSymbol retType = null)
        {
            SortedDictionary<int, MultiValueDictionary<TypeSymbol, Completion>> bases
                = new SortedDictionary<int, MultiValueDictionary<TypeSymbol, Completion>>();

            for (int score = 0;
                !parents.FullyComputed || score <= parents.MaxMinScore + DepthCoefficient ||
                pural && bases.Any(e => e.Key >= score - DepthCoefficient && e.Value.Any());
                score++)
            {
                yield return new MinFutureScore(score);
                cancellationToken.ThrowIfCancellationRequested();
                if (parents.ContainsKey(score))
                {
                    foreach (var p in parents[score])
                    {
                        if (retType.IsAssignableFromOrUnknown(p.Key, semModel))
                        {
                            foreach (var c in p.Value)
                            {
                                yield return c;
                            }
                        }
                    }
                }
                IEnumerable<KeyValuePair<TypeSymbol, SortedSet<Completion>>> basesForScore =
                    Enumerable.Empty<KeyValuePair<TypeSymbol, SortedSet<Completion>>>();
                int baseScore = score - DepthCoefficient;
                if (parents.ContainsKey(baseScore))
                {
                    basesForScore = parents[baseScore];
                }
                if (pural && bases.ContainsKey(baseScore))
                {
                    // TODO Really want to Merge or just Concat IEnumerables?
                    // The latter is faster if GetLookups is memoized.
                    basesForScore = basesForScore.Concat(bases[baseScore]);
                    bases.Remove(baseScore);
                }
                foreach (var p in basesForScore)
                {
                    if (pural)
                    {
                        foreach (var f in GetLookups(p.Key, fieldsOnly))
                        {
                            cancellationToken.ThrowIfCancellationRequested();
                            foreach (var c in p.Value.Where(c => c.AllowsLookups))
                            {
                                var res = new Completion(
                                    c.CompletionText + "." + f.CompletionText,
                                    f.Type,
                                    f.IsLValue,
                                    f.IsRValue,
                                    c.Score + DepthCoefficient,
                                    f.TypeTerm);
                                if (!bases.ContainsKey(res.Score))
                                {
                                    bases[res.Score] = new MultiValueDictionary<TypeSymbol, Completion>();
                                }
                                bases[res.Score].Add(res.Type, res);
                                if (retType.IsAssignableFromOrUnknown(res.Type, semModel))
                                {
                                    yield return res;
                                }
                            }
                        }
                    }
                    else
                    {
                        foreach (var f in GetLookups(p.Key, fieldsOnly, retType))
                        {
                            cancellationToken.ThrowIfCancellationRequested();
                            foreach (var c in p.Value.Where(c => c.AllowsLookups))
                            {
                                yield return new Completion(
                                    c.CompletionText + "." + f.CompletionText,
                                    f.Type,
                                    f.IsLValue,
                                    f.IsRValue,
                                    score,
                                    f.TypeTerm);
                            }
                        }
                    }
                }
            }
        }
        private IEnumerable<CompleterReturnValue> GetCompletions(MemberAccessExpressionSyntax acc,
            TypeSymbol retType = null)
        {
            var semInfo = semModel.GetTypeInfo(acc);
            var parentInfo = semModel.GetSymbolInfo(acc.Expression);
            var lookupName = acc.Name.GetText();
            if (!(parentInfo.Symbol is TypeSymbol)
                && !(semInfo.Type == null || semInfo.Type is ErrorTypeSymbol))
            {
                return new Completion(acc, semModel,
                                      absTypes.Value.GetTypeTermFor(acc, semModel)).Singleton();
            }
            else if (unknowns.Contains(lookupName)
                || (lookupName.EndsWith("Unknown")
                    && unknowns.Contains(lookupName.Substring(0, lookupName.Length - 7))))
            {
                bool pural = lookupName.Length > 1 && lookupName[1] != 'U'; // must be the second 'f' or 'x'
                bool fieldsOnly = lookupName[0] == 'f';
                // TODO This is a hack. Need to somehow check for there being no way to produce more items.
                /*if (fieldsOnly && retType != null && retType.SpecialType != null
                    && retType.SpecialType.Equals(SpecialType.System_Void))
                {
                    retType = null;
                }*/
                LazyCompletionsGetter parents;
                if (parentInfo.Symbol is TypeSymbol)
                {
                    var parentType = parentInfo.Symbol as TypeSymbol;
                    parents = new LazyCompletionsGetter(parentType.GetMembers()
                        .Where(sym => sym.IsStatic && (sym is PropertySymbol || sym is FieldSymbol))
                        .Select(sym => new Completion(sym, absTypes.Value.GetTypeTermFor(sym))));
                }
                else
                {
                    parents = new LazyCompletionsGetter(_GetCompletions(acc.Expression));
                }
                return GetCompletions(parents, fieldsOnly, pural, retType);
            }
            else
            {
                return new Completion(acc, semModel,
                                      absTypes.Value.GetTypeTermFor(acc, semModel)).Singleton();
            }
        }

        private IEnumerable<CompleterReturnValue> GetCompletionsUnknownMethod(
            IList<ExpressionSyntax> args, TypeSymbol retType, TypeSymbol parentStaticType = null)
        {
            /*return new List<string> { "? GetCompletionsUnknownMethod", args.CommaSeparated() }
                .Select(s => new Completion(s)).ToList();*/
            var argCompletions = args
                .Select(arg => new LazyCompletionsGetter(
                    _GetCompletions(arg)
                    .Where(c => !(c is Completion)
                        || ((c as Completion).IsRValue
                            && (c as Completion).Type.IsValidType()))))
                .ToList()
                .EnumerateSums();
            var suggestedMethods = new Dictionary<string, int>();
            foreach (var kv in argCompletions)
            {
                var argsCost = kv.Key;
                yield return new MinFutureScore(argsCost);
                cancellationToken.ThrowIfCancellationRequested();
                var argComps = kv.Value;
                foreach (var argComp in argComps)
                {
                    foreach (var argsConcreteCompletions in argComp.CartesianProductSingletons())
                    {
                        cancellationToken.ThrowIfCancellationRequested();

                        var argsConcreteList = argsConcreteCompletions
                            .Where(a => a.Key.IsValidType())
                            .ToList();
                        var argsTypesList = argsConcreteList.Select(a => a.Key).ToList();
                        foreach (var symbolGroup in GetMethodsForArgs(argsTypesList, parentStaticType)
                            .Where(s => retType.IsAssignableFromOrUnknown(s.ReturnType, semModel)
                                    && s.ReturnType.IsValidType()
                                    && s.ParameterTypes.All(p => p.Type.IsValidType()))
                            .GroupBy(s => s.ParameterTypes))
                        {
                            cancellationToken.ThrowIfCancellationRequested();

                            var paramTypes = symbolGroup.Key;

                            foreach (var assignmentSets in GetAssignmentsForArgs(paramTypes, argsConcreteList, true))
                            {
                                var argTypes = assignmentSets.Select(set => set.First().Type).ToList();
                                bool hasFirstArg = argTypes.Count >= 1
                                    && argTypes[0].IsValidType();

                                if (paramTypes.Zip(argTypes, (p, a) => !a.IsValidType() || p.IsCompatible(a, semModel)).All())
                                {
                                    int td = paramTypes
                                        .Zip(argTypes, (p, a) => a.IsValidType()
                                            ? p.Type.DistanceFrom(a, semModel)
                                            : 0)
                                        .Sum();
                                    int emptyPrefix = assignmentSets
                                        .TakeWhile(s => s.Count == 1
                                                     && s.First() is EmptyCompletion)
                                        .Count();
                                    int empty = assignmentSets
                                        .Count(s => s.Count == 1
                                                     && s.First() is EmptyCompletion);
                                    int emptyValueType = assignmentSets.Zip(paramTypes, (s,p) => 
                                        s.Count == 1
                                            && s.First() is EmptyCompletion
                                            && p.RefKind.Equals(RefKind.None)
                                            && p.Type.IsValueType).Count(b => b);
                                    int partialScore = argsCost
                                        + TypeDistanceCoefficient * td
                                        + EmptyPrefixCoefficient * emptyPrefix
                                        + EmptyCoefficient * empty;
                                    //var assignmentArrs = assignmentSets.Select(set => set.ToList()).ToList();
                                    foreach (var assignment in assignmentSets.CartesianProductSingletons())
                                    {
                                        var argStrList = assignment.Select(c => c.CompletionText);

                                        foreach (var symbol in symbolGroup)
                                        {
                                            TypeTerm symbolRetTT = symbol.GetReturnTypeTerm(absTypes.Value);
                                            string methodName = symbol.Name;
                                            if (symbol.IsStatic || hasFirstArg)
                                            {
                                                string str = symbol.ToString(argStrList);
                                                int absTD = assignment.Select((arg, i) =>
                                                    arg == null || arg is EmptyCompletion
                                                        || absTypes.Value.IsSameArg(arg, symbol, i) ? 0 : 1)
                                                   .Sum();
                                                int score = partialScore
                                                    + AbstractTypeDistanceCoefficient * absTD;
                                                int oldScore;
                                                if (!suggestedMethods.TryGetValue(methodName, out oldScore) || score < oldScore)
                                                {
                                                    yield return new Completion(str, symbol.ReturnType,
                                                        false, true, score, symbolRetTT, symbol,
                                                        new ScoreInfo() {
                                                            TypeDistance = td,
                                                            AbstractTypeDistance = absTD,
                                                            EmptyPrefix = emptyPrefix,
                                                            Empty = empty,
                                                            EmptyValueType = emptyValueType
                                                        });
                                                    suggestedMethods[methodName] = score;
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        private IEnumerable<CompleterReturnValue> GetCompletionsKnownMethod(IMethodSymbolWrapper symbol,
            List<ExpressionSyntax> args)
        {
            return GetCompletionsSemiKnownMethod(
                symbol.SingletonList<IMethodSymbolWrapper>(),
                args, symbol.ReturnType);
        }
        private IEnumerable<CompleterReturnValue> GetCompletionsSemiKnownMethod(List<IMethodSymbolWrapper> symbols,
            List<ExpressionSyntax> args, TypeSymbol retType)
        {
            var argCompletions = args
                .Select(arg => new LazyCompletionsGetter(
                    _GetCompletions(arg)
                    .Where(c => !(c is Completion) || (c as Completion).IsRValue)))
                .ToList()
                .EnumerateSumSets();
            foreach (var kv in argCompletions)
            {
                var argsCost = kv.Key;
                yield return new MinFutureScore(argsCost);
                cancellationToken.ThrowIfCancellationRequested();
                var argComps = kv.Value;
                foreach (var argComp in argComps)
                {
                    foreach (var argsConcreteCompletions in argComp.CartesianProductSingletons())
                    {
                        cancellationToken.ThrowIfCancellationRequested();

                        var argCompList = argsConcreteCompletions.ToList();
                        var argStrList = argCompList.Select(c => c.CompletionText).ToList();
                        var comps = new MultiValueDictionary<string, Completion>();
                        foreach (var symbol in symbols.Where(s => retType.IsAssignableFromOrUnknown(s.ReturnType, semModel)))
                        {
                            TypeTerm symbolRetTT = symbol.GetReturnTypeTerm(absTypes.Value);
                            var paramTypes = symbol.ParameterTypes;
                            if (paramTypes.Count >= argCompList.Count
                                && paramTypes.Zip(argCompList, (p, a) => !a.Type.IsValidType() || p.IsCompatible(a, semModel)).All())
                            {
                                var td = paramTypes
                                    .Zip(argCompList, (p, a) => a.Type.IsValidType()
                                        ? p.Type.DistanceFrom(a.Type, semModel)
                                        : 0)
                                    .Sum();
                                string str = symbol.ToString(argStrList);
                                int absTD = argCompList.Select((arg, i) =>
                                    arg == null || arg is EmptyCompletion
                                        || absTypes.Value.IsSameArg(arg, symbol, i) ? 0 : 1)
                                   .Sum();
                                int score = argsCost
                                    + TypeDistanceCoefficient * td
                                    + AbstractTypeDistanceCoefficient * absTD;
                                comps.Add(str, new Completion(str, symbol.ReturnType, score, symbolRetTT));
                            }
                        }
                        foreach (var compKV in comps)
                        {
                            yield return compKV.Value.Min;
                        }
                    }
                }
            }
        }

        // TODO Binary expressions, assignments, anything else? Arguments?
        private IEnumerable<CompleterReturnValue> GetAssignmentCompletions(BinaryExpressionSyntax exp,
                TypeSymbol retType)
        {
            var toSumList = new List<ExpressionSyntax> { exp.Left, exp.Right }
                    .Select((arg, i) => new LazyCompletionsGetter(
                        _GetCompletions(arg)
                        .Where(c => !(c is Completion)
                            || (i == 0 && (c as Completion).IsLValue)
                            || (i == 1 && (c as Completion).IsRValue))))
                    .ToList();
            var argCompletions = toSumList.EnumerateSumSets();

            foreach (var kv in argCompletions)
            {
                var argsCost = kv.Key;
                yield return new MinFutureScore(argsCost);
                cancellationToken.ThrowIfCancellationRequested();
                var argComps = kv.Value;
                foreach (var argComp in argComps)
                {
                    // TODO Grouping by type?
                    foreach (var argsConcreteCompletions in argComp.CartesianProductSingletons())
                    {
                        var argCompList = argsConcreteCompletions.ToList();
                        var argStrList = argCompList.Select(c => c.CompletionText).ToList();
                        if (!argStrList[0].Equals(argStrList[1])
                            && argCompList[0].Type.IsAssignableFromOrUnknown(argCompList[1].Type, semModel))
                        {
                            if (argCompList[1].Type.IsValidType() || !argCompList[0].Type.IsValidType())
                            {
                                var td = argCompList[0].Type.DistanceFrom(argCompList[1].Type, semModel);
                                string str = argStrList[0] + " = " + argStrList[1];
                                int absTD = absTypes.Value.IsSameAbstractType(argCompList[0].TypeTerm, argCompList[1].TypeTerm) ? 0 : 1;
                                //int absTD = argCompList.Select((arg, i) => arg == null || absTypes.IsSameArg(arg, symbol, i) ? 0 : 1).Sum();
                                //int absTD = 0;
                                int score = argsCost
                                    + TypeDistanceCoefficient * td
                                    + AbstractTypeDistanceCoefficient * absTD;
                                yield return new Completion(str, argCompList[0].Type, score, argCompList[0].TypeTerm);
                            }
                        }
                    }
                }
            }
        }
        private IEnumerable<CompleterReturnValue> GetCoalesceCompletions(BinaryExpressionSyntax exp,
                TypeSymbol retType)
        {
            var toSumList = new List<ExpressionSyntax> { exp.Left, exp.Right }
                    .Select(arg => new LazyCompletionsGetter(
                        _GetCompletions(arg)))
                    .ToList();
            var argCompletions = toSumList.EnumerateSumSets();

            foreach (var kv in argCompletions)
            {
                var argsCost = kv.Key;
                yield return new MinFutureScore(argsCost);
                cancellationToken.ThrowIfCancellationRequested();
                var argComps = kv.Value;
                foreach (var argComp in argComps)
                {
                    // TODO Grouping by type?
                    foreach (var argsConcreteCompletions in argComp.CartesianProductSingletons())
                    {
                        var argCompList = argsConcreteCompletions.ToList();
                        var argStrList = argCompList.Select(c => c.CompletionText).ToList();
                        TypeSymbol resType;
                        if (!argStrList[0].Equals(argStrList[1])
                            && argCompList[0].Type.CoalesceType(argCompList[1].Type, out resType, semModel))
                        {
                            if (retType.IsAssignableFromOrUnknown(retType, semModel))
                            {
                                var td = argCompList[0].Type.DistanceFrom(argCompList[1].Type, semModel);
                                string str = argStrList[0] + " = " + argStrList[1];
                                int absTD = absTypes.Value.IsSameAbstractType(argCompList[0].TypeTerm, argCompList[1].TypeTerm) ? 0 : 1;
                                int score = argsCost
                                    + TypeDistanceCoefficient * td
                                    + AbstractTypeDistanceCoefficient * absTD;
                                yield return new Completion(str, resType, score, argCompList[0].TypeTerm);
                            }
                        }
                    }
                }
            }
        }
        private static readonly Dictionary<string, string> opNames = new Dictionary<string, string>
            { 
                {">", "GreaterThan"},
                {">=", "GreaterThanOrEqual"},
                {"<", "LessThan"},
                {"<=", "LessThanOrEqual"},
                {"==", "Equality"},
                {"!=", "Inequality"},
                {"+", "Addition"},
                {"-", "Subtraction"},
                {"*", "Multiply"},
                {"/", "Division"},
                {"%", "Modulus"},
                {"<<", "LeftShift"},
                {">>", "RightShift"},
                {"&", "BitwiseAnd"},
                {"|", "BitwiseOr"},
                {"^", "ExclusiveOr"},
                {"&&", "LogicalAnd"},
                {"||", "LogicalOr"},
            };
        private IEnumerable<CompleterReturnValue> GetCompletions(BinaryExpressionSyntax exp,
                TypeSymbol retType)
        {
            if (exp.Kind.Equals(SyntaxKind.AssignExpression))
            {
                throw new Exception("Call GetAssignmentCompletions not GetCompletions.");
            }

            IList<IMethodSymbolWrapper> opSyms;
            List<TypeSymbol> intTypes = new List<SpecialType> {
                    SpecialType.System_Int32,
                    SpecialType.System_UInt32,
                    SpecialType.System_Int64, 
                    SpecialType.System_UInt64,
            }.Select(st => semModel.Compilation.GetSpecialType(st)).ToList<TypeSymbol>();
            List<TypeSymbol> numTypes = intTypes.Concat(new List<SpecialType> {
                    SpecialType.System_Single, 
                    SpecialType.System_Double, 
                    SpecialType.System_Decimal 
            }.Select(st => semModel.Compilation.GetSpecialType(st))).ToList<TypeSymbol>();
            TypeSymbol boolType = semModel.Compilation.GetSpecialType(SpecialType.System_Boolean);
            TypeSymbol int32Type = semModel.Compilation.GetSpecialType(SpecialType.System_Int32);
            TypeSymbol stringType = semModel.Compilation.GetSpecialType(SpecialType.System_String);

            string op = exp.OperatorToken.ValueText;
            if (!opNames.ContainsKey(op))
            {
                throw new Exception("Unknown operator: " + op);
            }
            string opName = opNames[op];

            switch (op)
            {
                case ">":
                case ">=":
                case "<":
                case "<=":
                    opSyms = numTypes.Select(nt => new BinaryOperatorSymbol(op, boolType,
                                                        nt, nt))
                                      .ToList<IMethodSymbolWrapper>();
                    break;
                case "==":
                case "!=":
                    opSyms = boolType.Cons(numTypes)
                                     .Select(t => new BinaryOperatorSymbol(op, boolType,
                                                        t, t))
                                     .ToList<IMethodSymbolWrapper>();
                    break;
                case "+":
                    opSyms = stringType.Cons(numTypes)
                                       .Select(t => new BinaryOperatorSymbol(op, t))
                                       .ToList<IMethodSymbolWrapper>();
                    break;
                case "-":
                case "*":
                case "/":
                case "%":
                    opSyms = numTypes.Select(nt => new BinaryOperatorSymbol(op, nt))
                                     .ToList<IMethodSymbolWrapper>();
                    break;
                case "<<":
                case ">>":
                    opSyms = intTypes.Select(it => new BinaryOperatorSymbol(op, it, it,
                                                                            int32Type))
                                     .ToList<IMethodSymbolWrapper>();
                    break;
                case "&":
                case "|":
                case "^":
                    opSyms = boolType.Cons(intTypes)
                                     .Select(t => new BinaryOperatorSymbol(op, t))
                                     .ToList<IMethodSymbolWrapper>();
                    break;
                case "&&":
                case "||":
                    opSyms = boolType.Singleton()
                                     .Select(t => new BinaryOperatorSymbol(op, t))
                                     .ToList<IMethodSymbolWrapper>();
                    break;
                default:
                    throw new Exception("Unknown binary operator: " + op);
            }

            string opMethName = "op_" + opName;
            var opMethodSyms = MethodUtil.GetAllStaticMethods(semModel)
                .Where(sym => sym.IsStatic && sym.Parameters.Count == 2
                    && sym.Name.Equals(opMethName))
                .Select(sym => new BinaryOpMethodSymbolWrapper(sym, op))
                .ToList<IMethodSymbolWrapper>();

            return GetCompletionsSemiKnownMethod(
                (opSyms.Concat(opMethodSyms)).ToList(),
                new List<ExpressionSyntax> { exp.Left, exp.Right },
                retType);
        }


        private IEnumerable<CompleterReturnValue> GetCompletions(
            ObjectCreationExpressionSyntax exp, TypeSymbol retType)
        {
            // Constructors never return void, so don't look for such results.
            if (retType != null && retType.Equals(semModel.Compilation.GetSpecialType(SpecialType.System_Void)))
            {
                retType = null;
            }
            var typeInfo = semModel.GetTypeInfo(exp.Type);
            if (!(typeInfo.Type is NamedTypeSymbol))
            {
                return new Completion(exp, semModel).Singleton();
            }
            var type = typeInfo.Type as NamedTypeSymbol;
            return GetCompletionsSemiKnownMethod(
                type.GetInstanceConstructors()
                    .Select(c => new MethodSymbolWrapper((MethodSymbol)c))
                    .ToList<IMethodSymbolWrapper>(),
                exp.ArgumentList.Arguments.Select(a => a.Expression).ToList(),
                retType);
            throw new NotImplementedException();
        }

        private IEnumerable<CompleterReturnValue> GetAsExpressionCompletions(
            BinaryExpressionSyntax exp)
        {
            var innerExp = exp.Left;

            var asTypeExp = exp.Right;
            TypeSymbol asType = semModel.GetSymbolInfo(asTypeExp).Symbol as TypeSymbol;
            string asTypeStr = asTypeExp.GetText();
            bool asTypeIsInterface = asType.TypeKind.Equals(TypeKind.Interface);

            foreach (CompleterReturnValue crv in _GetCompletions(innerExp, null))
            {
                if (crv is Completion)
                {
                    Completion c = crv as Completion;

                    // "as" is valid when a subtype of the left side expression may be
                    //      a subtype of the right side type.
                    // For class types, there is a tree, so this is the same as
                    //      if the left type is a subtype of the right type,
                    //      but for interfaces, there is no way to know.
                    var conversion = semModel.Compilation.ClassifyConversion(c.Type, asType);
                    // http://www.jaggersoft.com/csharp_standard/14.9.10.htm
                    if (conversion.IsIdentity
                        || conversion.IsBoxing
                        || ((conversion.IsImplicit || conversion.IsExplicit)
                            && conversion.IsReference))
                    /*if (asTypeIsInterface
                        || c.Type.TypeKind.Equals(TypeKind.Interface)
                        || c.Type.IsAssignableFromOrUnknown(asType, semModel))*/
                    {
                        // TODO Perserve type term?
                        yield return new Completion(
                            "(" + c.CompletionText + ") as " + asTypeStr,
                            asType, c.IsLValue, c.IsRValue, c.Score, c.TypeTerm);
                    }
                }
                else
                {
                    yield return crv;
                }
            }
        }

        private IEnumerable<CompleterReturnValue> WithTypeDistance(
                IEnumerable<CompleterReturnValue> xs,
                TypeSymbol retType,
                TypeTerm retTypeTerm)
        {
            bool validRetType = retType.IsValidType()
                && !retType.SpecialType.Equals(SpecialType.System_Void);
            foreach (CompleterReturnValue crv in xs)
            {
                if (crv is Completion)
                {
                    Completion c = crv as Completion;

                    // If we know the return type, filter out results of unknown type.
                    if (!validRetType || c.Type.IsValidType())
                    {
                        int td = !validRetType
                            ? 0
                            : retType.DistanceFrom(c.Type, semModel);
                        int absTd = retTypeTerm == null
                            || absTypes.Value.IsSameAbstractType(retTypeTerm, c.TypeTerm)
                                ? 0 : 1;

                        int newScore = c.Score
                            + td * TypeDistanceCoefficient
                            + absTd * AbstractTypeDistanceCoefficient;

                        yield return c.CloneWithScore(newScore);
                    }
                }
                else
                {
                    yield return crv;
                }
            }
        }

        public static IEnumerable<QueryResult<T>> PerformMethodQueries<T>(
            IEnumerable<MethodQuery<T>> queries, SemanticModel semModel,
            CancellationToken cancellationToken = default(CancellationToken))
        {
            MethodCache.SignalNewSemanticModel(semModel, cancellationToken);
            foreach(var query in queries)
            {
                var completer = new Completer(semModel, query.Position);
                yield return new QueryResult<T>(query,
                    completer.GetCompletions(
                        completer.GetCompletionsUnknownMethod(
                            query.Arguments, query.ReturnType, query.ParentStaticType),
                        query.ReturnType, query.IsLValue, query.AssignFromType));
            }
            MethodCache.SignalFinishedWithSemanticModel(semModel);
        }
    }

    public class MethodQuery<T>
    {
        private readonly InvocationExpressionSyntax originalMethodCall;
        private readonly MethodSymbol sym;
        private readonly int position;
        private readonly IList<ExpressionSyntax> args;
        private readonly bool isLValue;
        private readonly TypeSymbol retType, assignFrom;
        // Allow extra information to be stored along with query.
        private readonly T extraInfo;

        public MethodQuery(
            InvocationExpressionSyntax exp,
            MethodSymbol sym,
            IList<ExpressionSyntax> args,
            SemanticModel semModel,
            T extraInfo)
        {
            this.originalMethodCall = exp;
            this.sym = sym;
            this.args = args;
            this.extraInfo = extraInfo;
            this.position = exp.Span.Start;
            this.isLValue = exp.Parent.Kind.Equals(SyntaxKind.AssignExpression)
                    && (exp.Parent as BinaryExpressionSyntax).Left == exp;
            this.retType = exp.GetRetType(semModel);
            //this.parentStaticType = parentStaticType;

            if (this.isLValue)
            {
                this.assignFrom = semModel.GetTypeInfo((exp.Parent as BinaryExpressionSyntax).Right).Type;
            }
            else
            {
                this.assignFrom = null;
            }
        }

        public int Position { get { return position; } }
        public bool IsLValue { get { return isLValue; } }
        public TypeSymbol ReturnType { get { return retType; } }
        public TypeSymbol AssignFromType { get { return assignFrom; } }
        // TODO ?
        public TypeSymbol ParentStaticType { get { return null; } }
        public IList<ExpressionSyntax> Arguments { get { return args; } }
        public InvocationExpressionSyntax OriginalMethodCall { get { return originalMethodCall; } }
        public T ExtraInfo { get { return extraInfo; } }

        public bool IsCorrectAnswer(Completion c)
        {
            if (c.Method is MethodSymbolWrapper)
            {
                return sym.Equals(((MethodSymbolWrapper)c.Method).RealSymbol);
            }
            else
            {
                throw new NotImplementedException();
            }
        }
    }
    
    public class QueryResult<T>
    {
        private readonly MethodQuery<T> query;
        private readonly IEnumerable<Completion> results;

        public QueryResult(MethodQuery<T> query, IEnumerable<Completion> results)
        {
            this.query = query;
            this.results = results;
        }

        public MethodQuery<T> Query { get { return query; } }
        public IEnumerable<Completion> Results { get { return results; } }
    }
}
